package com.major.dawn.leetCode.array;

//如果实在确认排序的数组中丢失，我们能想到的最好方法，就是二分查找
public class SortArrayMissingNumber {

    public int missingNumber(int[] nums) {

        int length = nums.length;
        return dividePart(nums, 0, length - 1);
    }

    private Integer dividePart(int[] nums, int startIndex, int endIndex) {
        int missNum = 0;
        int endNum = nums[endIndex];

        int startNum = nums[startIndex];
        if (startIndex == endIndex) {
            if (startNum - nums[startIndex - 1] > 1) {
                return startIndex;
            }
            return 0;
        }

        if (endIndex - startIndex == 1) {

            if (endNum - startNum > 1) {
                return endNum;
            }

            if (startIndex > 0) {
                if (startNum - nums[startIndex - 1] > 1) {
                    return startNum;
                }
            }
            return 0;

        }

        int middleIndex = (startIndex + endIndex + 1) / 2;
        int curNum = nums[middleIndex];
        if (curNum == middleIndex) {
            missNum = dividePart(nums, middleIndex + 1, endIndex);
        }
        if (curNum > middleIndex) {
            if (curNum - nums[middleIndex - 1] > 1) {
                missNum = middleIndex;
            } else {
                missNum = dividePart(nums, startIndex, middleIndex - 1);
            }
        }
        return missNum;
    }

    public int missingNumber2(int[] nums) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{0,1,3,4,5};
        int length = nums.length;
        System.out.println(length);
        int middleIndex = (length + 1) / 2;
        System.out.println(middleIndex);

        SortArrayMissingNumber sortArrayMissingNumber = new SortArrayMissingNumber();
        int i = sortArrayMissingNumber.missingNumber2(nums);
        System.out.println(i);



    }
}
